package day2_linkedlist.leetcode;

/**
 * 反转部分链表
 *
 * @author yuisama
 * @date 2022/04/24 17:27
 **/
public class Num92_ReversePartOfLink {
    //    ListNode successor = null;
//    /**
//     * 反转以head为头节点的从left..right区间的子链表，返回反转后的头节点
//     * @param head
//     * @param left
//     * @param right
//     * @return
//     */
//    public ListNode reverseBetween(ListNode head, int left, int right) {
//        if (left == 1) {
//            return reverseN(head,right);
//        }
//        head.next = reverseBetween(head.next,left - 1,right - 1);
//        return head;
//    }
//
//    /**
//     * 反转以当前head为头节点的前n个节点的链表，返回反转后的头节点
//     * @param head
//     * @param n
//     * @return
//     */
//    public ListNode reverseN(ListNode head,int n) {
//        // 边界，若就是反转head节点，直接返回，记录n + 1个节点的地址
//        if (n == 1) {
//            successor = head.next;
//            return head;
//        }
//        ListNode next = head.next;
//        // 剩下n - 1个节点交给子函数
//        ListNode newHead = reverseN(head.next,n - 1);
//        next.next = head;
//        head.next = successor;
//        return newHead;
//    }
    // 迭代法
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        // prev指向带反转区间的前驱节点
        ListNode prev = dummyHead;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        // cur指向待反转区间的第一个节点
        ListNode cur = prev.next;
        // 只需要反转right - left次即可
        for (int i = 0; i < right - left; i++) {
            // 下一个要处理的节点
            ListNode next = cur.next;
            // 先删除next，在头插到prev的后面
            cur.next = next.next;
            // 头插
            next.next = prev.next;
            prev.next = next;
        }
        return dummyHead.next;
    }
}